package leetCode.offer34;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution1 implements Solution{


    @Override
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> array = new ArrayList<>();
        bSearch(root,target,result,array);
        return result;
    }


    /**
     * 前序遍历
     * @param root
     * @param target
     * @param result
     * @param array
     */
    public static void bSearch(TreeNode root,int target,List<List<Integer>> result,List<Integer> array) {
        if(root != null){
            target = target - root.val;
            array.add(root.val);
            if(root.left==null&&root.right==null&&target==0) {
                result.add(new ArrayList<>(array));
            }
            bSearch(root.left,target,result,array);
            bSearch(root.right,target,result,array);
            // 返回上一层，删除本层节点
            array.remove(array.size()-1);
        }
    }


    /**
     * 向树中添加节点(从上到下层次顺序添加)
     * @param data 添加的数值
     */
    public void add(Integer data ,TreeNode root) {
        if(data == null) data = 0;
        if(root.val==0){
            root.val = data;
        } else {
            //通过队列来辅助进行层次遍历
            Queue<TreeNode> queue = new LinkedList<>();
            //首先存入祖宗节点，因为层次遍历中它是第一个被遍历的
            queue.add(root);
            while(!queue.isEmpty()){
                boolean isSuccess = false;
                for(int i=queue.size();i>0;i--){
                    TreeNode node = queue.poll();
                    assert node != null;
                    if(node.left!=null) {
                        queue.add(node.left);
                    }else{
                        node.left = new TreeNode(data);
                        isSuccess = true;
                        break;
                    }
                    if(node.right!=null) {
                        queue.add(node.right);
                    }else{
                        node.right = new TreeNode(data);
                        isSuccess = true;
                        break;
                    }
                }
                if(isSuccess) break;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] params = {1,0,1,1,2,0,-1,0,1,-1,0,-1,0,1,0};
        TreeNode root = new TreeNode(0);
        Solution1 solution1 = new Solution1();
        for(Integer item:params){
            solution1.add(item,root);

        }
        int target = 2;
        System.out.println(solution1.pathSum(root,target));
    }

}
